package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:741. 摘樱桃
 * <p>
 * User:Mr.Du
 * Date:2024/5/6
 * Time:9:37
 */
public class CherryPickup {

    /**
     * 在二维网格中收获樱桃的最大小计。
     * 每个单元格中包含一个非负整数，代表在该位置收获的樱桃数量。起点位于左上角，目标是到达右下角，
     * 在一次移动中，可以向下或向右移动一格。要求在到达终点时不返回起点，并且在移动过程中可以选择收集或不收集樱桃。
     * 返回能够收集到的樱桃的最大数量。
     *
     * @param grid 表示樱桃分布的二维网格。
     * @return 能够收集到的樱桃的最大数量。
     */
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][] f = new int[n + 1][n + 1]; // 动态规划数组，f[i][j] 表示从起点到达坐标 (i, j) 时的最大收获量。
        for (int[] r : f) {
            Arrays.fill(r, Integer.MIN_VALUE); // 初始化动态规划数组，表示未访问的状态。
        }
        f[1][1] = grid[0][0]; // 初始化起点的收获量。

        // 动态规划过程，遍历所有可能的时间点（从 1 到 n*2-2）以确定在该时间点的最大收获量。
        for (int t = 1; t < n * 2 - 1; t++) {
            // j 和 k 分别表示在时间 t 时机器人的横纵坐标。
            for (int j = Math.min(t, n - 1); j >= Math.max(t - n + 1, 0); j--) {
                for (int k = Math.min(t, n - 1); k >= j; k--) {
                    // 如果在当前位置或对角线上的位置存在负数，表示无法通过，则将该位置的最大收获量设为最小整数。
                    if (grid[t - j][j] < 0 || grid[t - k][k] < 0) {
                        f[j + 1][k + 1] = Integer.MIN_VALUE;
                    } else {
                        // 计算从 (j, k) 移动到终点的最大收获量。
                        f[j + 1][k + 1] = Math.max(Math.max(f[j + 1][k + 1], f[j + 1][k]), Math.max(f[j][k + 1], f[j][k])) +
                                grid[t - j][j] + (k != j ? grid[t - k][k] : 0);
                    }
                }
            }
        }
        // 返回从起点到达终点的最大收获量，如果为负数则表示无法到达终点。
        return Math.max(f[n][n], 0);
    }


    public static void main(String[] args) {
        int[][] grid = {{0,1},{1,-1}};
        System.out.println(new CherryPickup().cherryPickup(grid));
    }
}
